翻訳と辞書 Words near each other ・ Mongardino ・ Mongarlowe River ・ Mongarlowe, New South Wales ・ Mongasht Rural District ・ Mongausy ・ Mongauzy ・ Mongavlin Castle ・ Mongbara ・ Mongbwalu ・ Mongchontoseong ・ Mongchontoseong Station ・ Mongdin ・ Monge (A601) ・ Monge (crater) ・ Monge (surname) ・ Monge array ・ Monge cone ・ Monge de Montaudon ・ Monge equation ・ Monge Island ・ Monge's theorem ・ Mongefossen ・ Mongella Bureau ・ Mongelli case ・ Mongenast Ministry ・ Monger ・ Monger (surname) ・ Mongeri ・ Monget ・ Mongewell Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Monge array ： ウィキペディア英語版 Monge array In mathematics applied to computer science, Monge arrays, or Monge matrices, are mathematical objects named for their discoverer, the French mathematician Gaspard Monge. An ''m''-by-''n'' matrix is said to be a ''Monge array'' if, for all $\backslash scriptstyle\; i,\backslash ,\; j,\backslash ,\; k,\backslash ,\; \backslash ell$ such that : one obtains :$A()\; +\; A()\; \backslash le\; A()\; +\; A().\backslash ,$ So for any two rows and two columns of a Monge array (a 2 × 2 sub-matrix) the four elements at the intersection points have the property that the sum of the upper-left and lower right elements (across the main diagonal) is less than or equal to the sum of the lower-left and upper-right elements (across the antidiagonal). This matrix is a Monge array: :$$ \begin 10 & 17 & 13 & 28 & 23 \\ 17 & 22 & 16 & 29 & 23 \\ 24 & 28 & 22 & 34 & 24 \\ 11 & 13 & 6 & 17 & 7 \\ 45 & 44 & 32 & 37 & 23 \\ 36 & 33 & 19 & 21 & 6 \\ 75 & 66 & 51 & 53 & 34 \end For example, take the intersection of rows 2 and 4 with columns 1 and 5. The four elements are: :$$ \begin 17 & 23\\ 11 & 7 \end : 17 + 7 = 24 : 23 + 11 = 34 The sum of the upper-left and lower right elements is less than or equal to the sum of the lower-left and upper-right elements. ==Properties== *The above definition is equivalent to the statement :A matrix is a Monge array if and only if $A()\; +\; A()\backslash le\; A()\; +\; A()$ for all and . *Any subarray produced by selecting certain rows and columns from an original Monge array will itself be a Monge array. *Any linear combination with non-negative coefficients of Monge arrays is itself a Monge array. *One interesting property of Monge arrays is that if you mark with a circle the leftmost minimum of each row, you will discover that your circles march downward to the right; that is to say, if $f(x)\; =\; \backslash arg\backslash min\_\{i\backslash in\; \backslash \{1,\backslash ldots,m\backslash \}\}\; A()$, then $f(j)\backslash le\; f(j+1)$ for all . Symmetrically, if you mark the uppermost minimum of each column, your circles will march rightwards and downwards. The row and column ''maxima'' march in the opposite direction: upwards to the right and downwards to the left. *The notion of ''weak Monge arrays'' has been proposed; a weak Monge array is a square ''n''-by-''n'' matrix which satisfies the Monge property $A()\; +\; A()\backslash le\; A()\; +\; A()$ only for all . *Every Monge array is totally monotone, meaning that its row minima occur in a nondecreasing sequence of columns, and that the same property is true for every subarray. This property allows the row minima to be found quickly by using the SMAWK algorithm. *Monge matrix is just another name for submodular function of two discrete variables. Precisely, ''A'' is a Monge matrix if and only if ''A''() is a submodular function of variables ''i'',''j''. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Monge array」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.